// Copyright (c) 2005-2008, Simon Howard
// Permission to use, copy, modify, and/or distribute this software for any purpose
// with or without fee is hereby granted, provided that the above copyright notice
// and this permission notice appear in all copies.
// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
// AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
// OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
// PERFORMANCE OF THIS SOFTWARE.

/// A double-ended queue (deque) implemented using a doubly linked list.
/// This deque allows pushing and popping elements from both the head and tail.
pub struct Deque<T> {
    head: Option<Box<Node<T>>>,
    tail: Option<*mut Node<T>>,
}

/// A node in the doubly linked list.
struct Node<T> {
    data: T,
    prev: Option<*mut Node<T>>,
    next: Option<Box<Node<T>>>,
}

impl<T> Deque<T> {
    /// Creates a new empty deque.
    pub fn new() -> Self {
        Deque { head: None, tail: None }
    }

    /// Checks if the deque is empty.
    pub fn is_empty(&self) -> bool {
        self.head.is_none()
    }

    /// Pushes an element to the head of the deque.
    pub fn push_head(&mut self, data: T) {
        let new_node = Box::new(Node {
            data,
            prev: None,
            next: self.head.take(),
        });

        let raw_node = Box::into_raw(new_node);

        if let Some(next) = unsafe { (*raw_node).next.as_mut() } {
            next.prev = Some(raw_node);
        } else {
            self.tail = Some(raw_node);
        }

        self.head = Some(unsafe { Box::from_raw(raw_node) });
    }

    /// Pushes an element to the tail of the deque.
    pub fn push_tail(&mut self, data: T) {
        let new_node = Box::new(Node {
            data,
            prev: self.tail,
            next: None,
        });

        let raw_node = Box::into_raw(new_node);

        if let Some(tail) = self.tail {
            unsafe { (*tail).next = Some(Box::from_raw(raw_node)) };
        } else {
            self.head = Some(unsafe { Box::from_raw(raw_node) });
        }

        self.tail = Some(raw_node);
    }

    /// Pops an element from the head of the deque.
    pub fn pop_head(&mut self) -> Option<T> {
        self.head.take().map(|mut head| {
            self.head = head.next.take();

            if let Some(next) = self.head.as_mut() {
                next.prev = None;
            } else {
                self.tail = None;
            }

            head.data
        })
    }

    /// Pops an element from the tail of the deque.
    pub fn pop_tail(&mut self) -> Option<T> {
        self.tail.take().and_then(|tail| {
            let tail_node = unsafe { Box::from_raw(tail) };

            if let Some(prev) = tail_node.prev {
                unsafe { (*prev).next = None };
                self.tail = Some(prev);
            } else {
                self.head = None;
                self.tail = None;
            }

            Some(tail_node.data)
        })
    }

    /// Peeks at the element at the head of the deque.
    pub fn peek_head(&self) -> Option<&T> {
        self.head.as_ref().map(|node| &node.data)
    }

    /// Peeks at the element at the tail of the deque.
    pub fn peek_tail(&self) -> Option<&T> {
        self.tail.and_then(|tail| unsafe { Some(&(*tail).data) })
    }
}

impl<T> Drop for Deque<T> {
    fn drop(&mut self) {
        while self.pop_head().is_some() {}
    }
}

#[cfg(test)]
mod tests {
    use super::Deque;

    #[test]
    fn test_push_pop_head() {
        let mut deque: Deque<i32> = Deque::new();
        deque.push_head(1);
        deque.push_head(2);
        assert_eq!(deque.pop_head(), Some(2));
        assert_eq!(deque.pop_head(), Some(1));
        assert_eq!(deque.pop_head(), None);
    }

    #[test]
    fn test_push_pop_tail() {
        let mut deque: Deque<i32> = Deque::new();
        deque.push_tail(1);
        deque.push_tail(2);
        assert_eq!(deque.pop_tail(), Some(2));
        assert_eq!(deque.pop_tail(), Some(1));
        assert_eq!(deque.pop_tail(), None);
    }

    #[test]
    fn test_peek_head_tail() {
        let mut deque: Deque<i32> = Deque::new();
        deque.push_head(1);
        deque.push_tail(2);
        assert_eq!(deque.peek_head(), Some(&1));
        assert_eq!(deque.peek_tail(), Some(&2));
    }

    #[test]
    fn test_is_empty() {
        let mut deque: Deque<i32> = Deque::new();
        assert!(deque.is_empty());
        deque.push_head(1);
        assert!(!deque.is_empty());
        deque.pop_head();
        assert!(deque.is_empty());
    }
}
